class Solution {
public:
    int uniquePaths(int m, int n) {
            //初始化
    vector<vector<int>> f(m,vector<int>(n) );

    for (int i = 0;i < n;i++)
    {
        f[0][i] = 1;
    }

    for (int j = 0;j < m;j++)
    {
        f[j][0] = 1;
    }
    //有了初始值就累加
    for (int i = 1;i < m;i++)
    {
        for (int j = 1;j < n;j++)
        {
            f[i][j] = f[i - 1][j] + f[i][j-1];
        }
    }

    return f[m - 1][n - 1];
    }
};

#if 0
//从1，1点走到m,n的所有路径 （暴力递归来一次）
//自己转换不过的原因：局限于用加1的方式记录条数，不知如何表示右边和下边遍历的分支，递归条件知道却不知如何表示，其实的递加变量不清楚
int Recursive(int x,int y,int m,int n)
{
    int ret = 0;
    //递归结束条件
    if (x == m && y == n)
    {
        return 1;
    }
    else
    {
        if ((x + 1) <= m)
        {
            ret +=  Recursive(x + 1, y, m, n);
        }

        if ((y + 1) <= n)
        {
            ret += Recursive(x, y + 1, m, n);
        }
    }

    return ret;

}
void AllWay(int m, int n)
{
    int ret = 0;
    ret = ret + Recursive(1, 1, m, n);
    printf("递归结果：%d \n",ret);
}
#endif
